НАВЧАЛЬНЕ ВИДАННЯ
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
Методичні вказівкидо лабораторної роботи N3 курсу "Організація баз даних і знань"для студентiв базового напрямку "Комп’ютернi науки
Укладачi Керницький Андрій Богданович
Мотика Ігор Іванович
Стех Юрій Васильович
Редактор Черничевич О.
МIНIСТЕРСТВО ОСВIТИ І НАУКИ УКРАЇНИ
Національний унiверситет "Львiвська полiтехнiка"
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи N 3
з курсу "Організація баз даних і знань "
для студентiв базового напрямку 6.0804
"Комп'ютернi науки"
Затверджено на засiданнi кафедри Системи автоматизованого проектування"
Протокол N14 вiд 03.04.1997р.
Львiв 2002
ІНДЕКСНО-ПОСЛІДОВНИЙ МЕТОД ДОСТУПУ ДО ФАЙЛІВ НА ЗОВНІШНІХ ЗАПАМ’ЯТОВУЮЧИХ ПРИСТРОЯХ: Методичні вказівки до лабораторної роботи N3 з курсу " Організація баз даниз і знань " для студентiв базового напрямку "Комп'ютернi науки" / Укл. А.Б.Керницький, І.І.Мотика, Ю.В.Стех. - Львiв: НУЛП, 2002.-10с.
Укладачi: А.Б.Керницький, маг.техн.наук.
І.І.Мотика, канд.техн.наук,доц.,
Ю.В.Стех, канд.техн.наук, доц.
Вiдповiдальний за випуск С.П.Ткаченко, канд.техн.наук, доц.
Рецензенти: М.Б.Близнюк, канд.техн.наук, доц.
I.I.Чура, канд.техн.наук, доц.
Додаток
ІНДИВІДУАЛЬНЕ ЗАВДАННЯ
1. Написати програму, яка реалiзує алгоритми роботи iндексно-послiдов ного методу доступу до iнформацiї на зовнiшнiх носiях:
1.1. Пошук елемента даних за введеним ключем.
1.2. Вставка елемента даних.
1.3. Видалення елемента даних.
1.4. Модифiкацiя елемента даних.
2. Варіанти файлів даних:
- студентська група,
- кафедра САП,
- НУЛП,
- футбольна лiга,
- прокат авто,
- мережа кiнотеатрiв.
11
3. КОНТРОЛЬНІ ЗАПИТАННЯ
Як органiзовується iндексний файл?
Чому швидкодiя пошуку у iндексному файлі вища?
Як здiйснюється пошук в iндексi?
Як здiйснюється вставка нового елемента даних при iндексно-послiдовному методi?
Що таке ділянка переповнення?
Як органiзовується багатоiєрархiчна адресацiя?
Як організовується видалення при iндексно-послiдовному методi?
10
1. МЕТА РОБОТИ
озглянути органiзацiю i ведення файлiв iндексно-послiдовного доступу; набути практичнi навички у програмуваннi алгоритмiв iндексно-послiдовного доступу до файлiв на зовнiшнiх запам'ятовуючих пристроях.
2. КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
Якщо файл впорядкований по ключах, то звичайно для адресацiї використовується таблиця, що називається iндексом. При звертаннi до таблицi задається ключ шуканого запису, а результатом процедури пошуку у таблицi є вiдносна адреса запису у зовнiшнiй пам'ятi.
Якщо для адресацiї файла використовується iндекс, ЕОМ в основному здiйснює пошук в iндексi, а не у файлi даних. При цьому суттєво економиться час, але потребується пам'ять для зберiгання iндексу.
Існує багато iндексних методiв доступу, в основi яких лежить принцип створення окремого iндексного файла. індексний файл значно менший вiд власне бази даних, i, оскiльки вiн може повнiстю зберiгатися в оперативнiй пам'ятi, швидкодiя пошуку у ньому значно вища.
В iндексно-послiдовному методi доступу iндексний файл завжди впорядкований за так званим первинним ключем (головний атрибут фiзичного запису).
Оскiльки у цьому методi i записи файла даних впорядкованi за ключем, iндекс звичайно мiстить не посилання на окремий запис, а посилання на блоки записiв, всерединi яких можна здiйснювати пошук i сканування. Збереження посилань на блоки записiв, а не на окремi записи значно зменшує розмiр iндексу. Наприклад, якщо в блоцi зберiгається 10 записiв, то для нього в iндексному файлi буде одна стаття, а не 10, i розмiр iндексного файла зменшується в 10 разiв.
3
745
756
781
867
875
879
899
904
910
Блок2
Блок3
Блок1
Індексний файл
Ф...